from collections import deque

# 定义目标状态
goal_state = [[1, 2, 3],
              [4, 5, 6],
              [7, 8, 0]]

# 定义移动方向：上、下、左、右
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]


def bfs(start_state):
    # 将初始状态转化为二维列表
    start_state = [list(row) for row in start_state]

    # 定义队列，存放待扩展的状态
    queue = deque([(start_state, "")])
    visited = set()

    while queue:
        current_state, path = queue.popleft()

        if current_state == goal_state:
            return path

        # 找到空白格的位置
        for i in range(3):
            for j in range(3):
                if current_state[i][j] == 0:
                    x, y = i, j

        # 尝试移动空白格
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            if 0 <= nx < 3 and 0 <= ny < 3:
                # 生成新状态
                new_state = [row[:] for row in current_state]
                new_state[x][y], new_state[nx][ny] = new_state[nx][ny], new_state[x][y]
                new_path = path + "UDLR"[directions.index((dx, dy))]

                # 如果新状态未访问过，则加入队列
                if tuple(map(tuple, new_state)) not in visited:
                    visited.add(tuple(map(tuple, new_state)))
                    queue.append((new_state, new_path))

    return "No solution found."


# 示例输入
start_state = [[1, 2, 3],
               [4, 0, 6],
               [7, 5, 8]]

# 调用广度优先搜索算法
solution = bfs(start_state)

print("解决方案:", solution)
